class Solution(object):
    def minimumTeachings(self, n, languages, friendships):
        languages = [set(l) for l in languages]
        min_t = float('inf')
        st = []
        for u, v in friendships:
            if not languages[u - 1] & languages[v - 1]:
                st.append([u, v])
        for i in range(1, n + 1):
            ans = 0
            learned = set()
            for u, v in st:
                if i not in languages[u - 1] and u - 1 not in learned:
                    learned.add(u - 1)
                    ans += 1
                if i not in languages[v - 1] and v - 1 not in learned:
                    learned.add(v - 1)
                    ans += 1
            min_t = min(min_t, ans)
        return min_t